#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("cover.in" , "r" , stdin);
	freopen("cover.out" , "w" , stdout);
	int n;
	cin >> n;
	int f[1010];
	f[1] = 1;
	f[2] = 3;
	for(int i = 3 ; i <= n ; i++){
		f[i] = f[i - 1] + 2 * f[i - 2];
		f[i] %= 12345;
	}
	cout << f[n] << endl;
	return 0;
}
